/*
 * Copyright (C) 2007-2017 Diego Perini
 * All rights reserved.
 *
 * nwmatcher.js - A fast CSS selector engine and matcher
 *
 * Author: Diego Perini <diego.perini at gmail com>
 * Version: 1.4.3
 * Created: 20070722
 * Release: 20171011
 *
 * License:
 *  http://javascript.nwbox.com/NWMatcher/MIT-LICENSE
 * Download:
 *  http://javascript.nwbox.com/NWMatcher/nwmatcher.js
 */

(function(global, factory) {

    if (typeof module == 'object' && typeof exports == 'object') {
        module.exports = factory;
    } else if (typeof define === 'function' && define["amd"]) {
        define(factory);
    } else {
        global.NW || (global.NW = { });
        global.NW.Dom = factory(global);
    }

})(this, function(global) {

    var version = 'nwmatcher-1.4.3',

        // processing context & root element
        doc = global.document,
        root = doc.documentElement,

        // save utility methods references
        slice = [ ].slice,

        // persist previous parsed data
        isSingleMatch,
        isSingleSelect,

        lastSlice,
        lastContext,
        lastPosition,

        lastMatcher,
        lastSelector,

        lastPartsMatch,
        lastPartsSelect,

        // accepted prefix identifiers
        // (id, class & pseudo-class)
        prefixes = '(?:[#.:]|::)?',

        // accepted attribute operators
        operators = '([~*^$|!]?={1})',

        // accepted whitespace characters
        whitespace = '[\\x20\\t\\n\\r\\f]',

        // 4 combinators F E, F>E, F+E, F~E
        combinators = '\\x20|[>+~](?=[^>+~])',

        // an+b format params for pseudo-classes
        pseudoparms = '(?:[-+]?\\d*n)?[-+]?\\d*',

        // skip [ ], ( ), { } brackets groups
        skip_groups = '\\[.*\\]|\\(.*\\)|\\{.*\\}',

        // any escaped char
        any_esc_chr = '\\\\.',
        // alpha chars & low dash
        alphalodash = '[_a-zA-Z]',
        // non-ascii chars (utf-8)
        non_asc_chr = '[^\\x00-\\x9f]',
        // escape sequences in strings
        escaped_chr = '\\\\[^\\n\\r\\f0-9a-fA-F]',
        // Unicode chars including trailing whitespace
        unicode_chr = '\\\\[0-9a-fA-F]{1,6}(?:\\r\\n|' + whitespace + ')?',

        // CSS quoted string values
        quotedvalue = '"[^"\\\\]*(?:\\\\.[^"\\\\]*)*"' + "|'[^'\\\\]*(?:\\\\.[^'\\\\]*)*'",

        // regular expression used to skip single/nested brackets groups (round, square, curly)
        // used to split comma groups excluding commas inside quotes '' "" or brackets () [] {}
        reSplitGroup = /([^,\\()[\]]+|\[[^[\]]*\]|\[.*\]|\([^()]+\)|\(.*\)|\{[^{}]+\}|\{.*\}|\\.)+/g,

        // regular expression to trim extra leading/trailing whitespace in selector strings
        // whitespace is any combination of these 5 character [\x20\t\n\r\f]
        // http://www.w3.org/TR/css3-selectors/#selector-syntax
        reTrimSpaces = RegExp('[\\n\\r\\f]|^' + whitespace + '+|' + whitespace + '+$', 'g'),

        // regular expression used in convertEscapes and unescapeIdentifier
        reEscapedChars = /\\([0-9a-fA-F]{1,6}[\x20\t\n\r\f]?|.)|([\x22\x27])/g,

        // for in excess whitespace removal
        reWhiteSpace = /[\x20\t\n\r\f]+/g,

        standardValidator, extendedValidator, reValidator,

        attrcheck, attributes, attrmatcher, pseudoclass,

        reOptimizeSelector, reSimpleNot, reSplitToken,

        Optimize, reClass, reSimpleSelector,

        // http://www.w3.org/TR/css3-syntax/#characters
        // unicode/ISO 10646 characters \xA0 and higher
        // NOTE: Safari 2.0.x crashes with escaped (\\)
        // Unicode ranges in regular expressions so we
        // use a negated character range class instead
        // now assigned at runtime from config options
        identifier,

        // placeholder for extensions
        extensions = '.+',

        // precompiled Regular Expressions
        Patterns = {
            // structural pseudo-classes and child selectors
            spseudos: /^\:(root|empty|(?:first|last|only)(?:-child|-of-type)|nth(?:-last)?(?:-child|-of-type)\(\s*(even|odd|(?:[-+]{0,1}\d*n\s*)?[-+]{0,1}\s*\d*)\s*\))?(.*)/i,
            // uistates + dynamic + negation pseudo-classes
            dpseudos: /^\:(link|visited|target|active|focus|hover|checked|disabled|enabled|selected|lang\(([-\w]{2,})\)|(?:matches|not)\(\s*(:nth(?:-last)?(?:-child|-of-type)\(\s*(?:even|odd|(?:[-+]{0,1}\d*n\s*)?[-+]{0,1}\s*\d*)\s*\)|[^()]*)\s*\))?(.*)/i,
            // pseudo-elements selectors
            epseudos: /^((?:[:]{1,2}(?:after|before|first-letter|first-line))|(?:[:]{2,2}(?:selection|backdrop|placeholder)))?(.*)/i,
            // E > F
            children: RegExp('^' + whitespace + '*\\>' + whitespace + '*(.*)'),
            // E + F
            adjacent: RegExp('^' + whitespace + '*\\+' + whitespace + '*(.*)'),
            // E ~ F
            relative: RegExp('^' + whitespace + '*\\~' + whitespace + '*(.*)'),
            // E F
            ancestor: RegExp('^' + whitespace + '+(.*)'),
            // all
            universal: RegExp('^\\*(.*)')
        },

        Tokens = {
            prefixes: prefixes,
            identifier: identifier,
            attributes: attributes
        },

        /*----------------------------- FEATURE TESTING ----------------------------*/

        // detect native methods
        isNative = (function() {
            var re = / \w+\(/,
                isnative = String(({ }).toString).replace(re, ' (');
            return function(method) {
                return method && typeof method != 'string' &&
                    isnative == String(method).replace(re, ' (');
            };
        })(),

        // NATIVE_XXXXX true if method exist and is callable
        // detect if DOM methods are native in browsers
        NATIVE_FOCUS = isNative(doc.hasFocus),
        NATIVE_QSAPI = isNative(doc.querySelector),
        NATIVE_GEBID = isNative(doc.getElementById),
        NATIVE_GEBTN = isNative(root.getElementsByTagName),
        NATIVE_GEBCN = isNative(root.getElementsByClassName),

        // detect native getAttribute/hasAttribute methods,
        // frameworks extend these to elements, but it seems
        // this does not work for XML namespaced attributes,
        // used to check both getAttribute/hasAttribute in IE
        NATIVE_GET_ATTRIBUTE = isNative(root.getAttribute),
        NATIVE_HAS_ATTRIBUTE = isNative(root.hasAttribute),

        // check if slice() can convert nodelist to array
        // see http://yura.thinkweb2.com/cft/
        NATIVE_SLICE_PROTO =
            (function() {
                var isBuggy = false;
                try {
                    isBuggy = !!slice.call(doc.childNodes, 0)[0];
                } catch(e) { }
                return isBuggy;
            })(),

        // supports the new traversal API
        NATIVE_TRAVERSAL_API =
            'nextElementSibling' in root && 'previousElementSibling' in root,

        // BUGGY_XXXXX true if method is feature tested and has known bugs
        // detect buggy gEBID
        BUGGY_GEBID = NATIVE_GEBID ?
            (function() {
                var isBuggy = true, x = 'x' + String(+new Date),
                    a = doc.createElementNS ? 'a' : '<a name="' + x + '">';
                (a = doc.createElement(a)).name = x;
                root.insertBefore(a, root.firstChild);
                isBuggy = !!doc.getElementById(x);
                root.removeChild(a);
                return isBuggy;
            })() :
            true,

        // detect IE gEBTN comment nodes bug
        BUGGY_GEBTN = NATIVE_GEBTN ?
            (function() {
                var div = doc.createElement('div');
                div.appendChild(doc.createComment(''));
                return !!div.getElementsByTagName('*')[0];
            })() :
            true,

        // detect Opera gEBCN second class and/or UTF8 bugs as well as Safari 3.2
        // caching class name results and not detecting when changed,
        // tests are based on the jQuery selector test suite
        BUGGY_GEBCN = NATIVE_GEBCN ?
            (function() {
                var isBuggy, div = doc.createElement('div'), test = '\u53f0\u5317';

                // Opera tests
                div.appendChild(doc.createElement('span')).
                setAttribute('class', test + 'abc ' + test);
                div.appendChild(doc.createElement('span')).
                setAttribute('class', 'x');

                isBuggy = !div.getElementsByClassName(test)[0];

                // Safari test
                div.lastChild.className = test;
                return isBuggy || div.getElementsByClassName(test).length != 2;
            })() :
            true,

        // detect IE bug with dynamic attributes
        BUGGY_GET_ATTRIBUTE = NATIVE_GET_ATTRIBUTE ?
            (function() {
                var input = doc.createElement('input');
                input.setAttribute('value', 5);
                return input.defaultValue != 5;
            })() :
            true,

        // detect IE bug with non-standard boolean attributes
        BUGGY_HAS_ATTRIBUTE = NATIVE_HAS_ATTRIBUTE ?
            (function() {
                var option = doc.createElement('option');
                option.setAttribute('selected', 'selected');
                return !option.hasAttribute('selected');
            })() :
            true,

        // detect Safari bug with selected option elements
        BUGGY_SELECTED =
            (function() {
                var select = doc.createElement('select');
                select.appendChild(doc.createElement('option'));
                return !select.firstChild.selected;
            })(),

        // initialized with the loading context
        // and reset for each different context
        BUGGY_QUIRKS_GEBCN,
        BUGGY_QUIRKS_QSAPI,

        QUIRKS_MODE,
        XML_DOCUMENT,

        // detect Opera browser
        OPERA = typeof global.opera != 'undefined' &&
            (/opera/i).test(({ }).toString.call(global.opera)),

        // skip simple selector optimizations for Opera >= 11
        OPERA_QSAPI = OPERA && parseFloat(global.opera.version()) >= 11,

        // check Selector API implementations
        RE_BUGGY_QSAPI = NATIVE_QSAPI ?
            (function() {
                var pattern = [ ], context, element,

                    expect = function(selector, element, n) {
                        var result = false;
                        context.appendChild(element);
                        try { result = context.querySelectorAll(selector).length == n; } catch(e) { }
                        while (context.firstChild) { context.removeChild(context.firstChild); }
                        return result;
                    };

                // certain bugs can only be detected in standard documents
                // to avoid writing a live loading document create a fake one
                if (doc.implementation && doc.implementation.createDocument) {
                    // use a shadow document body as context
                    context = doc.implementation.createDocument('', '', null).
                    appendChild(doc.createElement('html')).
                    appendChild(doc.createElement('head')).parentNode.
                    appendChild(doc.createElement('body'));
                } else {
                    // use an unattached div node as context
                    context = doc.createElement('div');
                }

                // fix for Safari 8.x and other engines that
                // fail querying filtered sibling combinators
                element = doc.createElement('div');
                element.innerHTML = '<p id="a"></p><br>';
                expect('p#a+*', element, 0) &&
                pattern.push('\\w+#\\w+.*[+~]');

                // ^= $= *= operators bugs with empty values (Opera 10 / IE8)
                element = doc.createElement('p');
                element.setAttribute('class', '');
                expect('[class^=""]', element, 1) &&
                pattern.push('[*^$]=[\\x20\\t\\n\\r\\f]*(?:""|' + "'')");

                // :checked bug with option elements (Firefox 3.6.x)
                // it wrongly includes 'selected' options elements
                // HTML5 rules says selected options also match
                element = doc.createElement('option');
                element.setAttribute('selected', 'selected');
                expect(':checked', element, 0) &&
                pattern.push(':checked');

                // :enabled :disabled bugs with hidden fields (Firefox 3.5)
                // http://www.w3.org/TR/html5/links.html#selector-enabled
                // http://www.w3.org/TR/css3-selectors/#enableddisabled
                // not supported by IE8 Query Selector
                element = doc.createElement('input');
                element.setAttribute('type', 'hidden');
                expect(':enabled', element, 0) &&
                pattern.push(':enabled', ':disabled');

                // :link bugs with hyperlinks matching (Firefox/Safari)
                element = doc.createElement('link');
                element.setAttribute('href', 'x');
                expect(':link', element, 1) ||
                pattern.push(':link');

                // avoid attribute selectors for IE QSA
                if (BUGGY_HAS_ATTRIBUTE) {
                    // IE fails in reading:
                    // - original values for input/textarea
                    // - original boolean values for controls
                    pattern.push('\\[[\\x20\\t\\n\\r\\f]*(?:checked|disabled|ismap|multiple|readonly|selected|value)');
                }

                return pattern.length ?
                    RegExp(pattern.join('|')) :
                    { 'test': function() { return false; } };

            })() :
            true,

        /*----------------------------- LOOKUP OBJECTS -----------------------------*/

        IE_LT_9 = typeof doc.addEventListener != 'function',

        LINK_NODES = { 'a': 1, 'A': 1, 'area': 1, 'AREA': 1, 'link': 1, 'LINK': 1 },

        // boolean attributes should return attribute name instead of true/false
        ATTR_BOOLEAN = {
            'checked': 1, 'disabled': 1, 'ismap': 1,
            'multiple': 1, 'readonly': 1, 'selected': 1
        },

        // dynamic attributes that needs to be checked against original HTML value
        ATTR_DEFAULT = {
            'value': 'defaultValue',
            'checked': 'defaultChecked',
            'selected': 'defaultSelected'
        },

        // attributes referencing URI data values need special treatment in IE
        ATTR_URIDATA = {
            'action': 2, 'cite': 2, 'codebase': 2, 'data': 2, 'href': 2,
            'longdesc': 2, 'lowsrc': 2, 'src': 2, 'usemap': 2
        },

        // HTML 5 draft specifications
        // http://www.whatwg.org/specs/web-apps/current-work/#selectors
        HTML_TABLE = {
            // NOTE: class name attribute selectors must always be treated using a
            // case-sensitive match, this has changed from previous specifications
            'accept': 1, 'accept-charset': 1, 'align': 1, 'alink': 1, 'axis': 1,
            'bgcolor': 1, 'charset': 1, 'checked': 1, 'clear': 1, 'codetype': 1, 'color': 1,
            'compact': 1, 'declare': 1, 'defer': 1, 'dir': 1, 'direction': 1, 'disabled': 1,
            'enctype': 1, 'face': 1, 'frame': 1, 'hreflang': 1, 'http-equiv': 1, 'lang': 1,
            'language': 1, 'link': 1, 'media': 1, 'method': 1, 'multiple': 1, 'nohref': 1,
            'noresize': 1, 'noshade': 1, 'nowrap': 1, 'readonly': 1, 'rel': 1, 'rev': 1,
            'rules': 1, 'scope': 1, 'scrolling': 1, 'selected': 1, 'shape': 1, 'target': 1,
            'text': 1, 'type': 1, 'valign': 1, 'valuetype': 1, 'vlink': 1
        },

        /*-------------------------- REGULAR EXPRESSIONS ---------------------------*/

        // placeholder to add functionalities
        Selectors = {
            // as a simple example this will check
            // for chars not in standard ascii table
            //
            // 'mySpecialSelector': {
            //  'Expression': /\u0080-\uffff/,
            //  'Callback': mySelectorCallback
            // }
            //
            // 'mySelectorCallback' will be invoked
            // only after passing all other standard
            // checks and only if none of them worked
        },

        // attribute operators
        Operators = {
            '=': "n=='%m'",
            '^=': "n.indexOf('%m')==0",
            '*=': "n.indexOf('%m')>-1",
            '|=': "(n+'-').indexOf('%m-')==0",
            '~=': "(' '+n+' ').indexOf(' %m ')>-1",
            '$=': "n.substr(n.length-'%m'.length)=='%m'"
        },

        /*------------------------------ UTIL METHODS ------------------------------*/

        // concat elements to data
        concatList =
            function(data, elements) {
                var i = -1, element;
                if (!data.length && Array.slice)
                    return Array.slice(elements);
                while ((element = elements[++i]))
                    data[data.length] = element;
                return data;
            },

        // concat elements to data and callback
        concatCall =
            function(data, elements, callback) {
                var i = -1, element;
                while ((element = elements[++i])) {
                    if (false === callback(data[data.length] = element)) { break; }
                }
                return data;
            },

        // change context specific variables
        switchContext =
            function(from, force) {
                var div, oldDoc = doc;
                // save passed context
                lastContext = from;
                // set new context document
                doc = from.ownerDocument || from;
                if (force || oldDoc !== doc) {
                    // set document root
                    root = doc.documentElement;
                    // set host environment flags
                    XML_DOCUMENT = doc.createElement('DiV').nodeName == 'DiV';

                    // In quirks mode css class names are case insensitive.
                    // In standards mode they are case sensitive. See docs:
                    // https://developer.mozilla.org/en/Mozilla_Quirks_Mode_Behavior
                    // http://www.whatwg.org/specs/web-apps/current-work/#selectors
                    QUIRKS_MODE = !XML_DOCUMENT &&
                    typeof doc.compatMode == 'string' ?
                        doc.compatMode.indexOf('CSS') < 0 :
                        (function() {
                            var style = doc.createElement('div').style;
                            return style && (style.width = 1) && style.width == '1px';
                        })();

                    div = doc.createElement('div');
                    div.appendChild(doc.createElement('p')).setAttribute('class', 'xXx');
                    div.appendChild(doc.createElement('p')).setAttribute('class', 'xxx');

                    // GEBCN buggy in quirks mode, match count is:
                    // Firefox 3.0+ [xxx = 1, xXx = 1]
                    // Opera 10.63+ [xxx = 0, xXx = 2]
                    BUGGY_QUIRKS_GEBCN =
                        !XML_DOCUMENT && NATIVE_GEBCN && QUIRKS_MODE &&
                        (div.getElementsByClassName('xxx').length != 2 ||
                            div.getElementsByClassName('xXx').length != 2);

                    // QSAPI buggy in quirks mode, match count is:
                    // At least Chrome 4+, Firefox 3.5+, Opera 10.x+, Safari 4+ [xxx = 1, xXx = 2]
                    // Safari 3.2 QSA doesn't work with mixedcase in quirksmode [xxx = 1, xXx = 0]
                    // https://bugs.webkit.org/show_bug.cgi?id=19047
                    // must test the attribute selector '[class~=xxx]'
                    // before '.xXx' or the bug may not present itself
                    BUGGY_QUIRKS_QSAPI =
                        !XML_DOCUMENT && NATIVE_QSAPI && QUIRKS_MODE &&
                        (div.querySelectorAll('[class~=xxx]').length != 2 ||
                            div.querySelectorAll('.xXx').length != 2);

                    Config.CACHING && Dom.setCache(true, doc);
                }
            },

        // convert single codepoint to UTF-16 encoding
        codePointToUTF16 =
            function(codePoint) {
                // out of range, use replacement character
                if (codePoint < 1 || codePoint > 0x10ffff ||
                    (codePoint > 0xd7ff && codePoint < 0xe000)) {
                    return '\\ufffd';
                }
                // javascript strings are UTF-16 encoded
                if (codePoint < 0x10000) {
                    var lowHex = '000' + codePoint.toString(16);
                    return '\\u' + lowHex.substr(lowHex.length - 4);
                }
                // supplementary high + low surrogates
                return '\\u' + (((codePoint - 0x10000) >> 0x0a) + 0xd800).toString(16) +
                    '\\u' + (((codePoint - 0x10000) % 0x400) + 0xdc00).toString(16);
            },

        // convert single codepoint to string
        stringFromCodePoint =
            function(codePoint) {
                // out of range, use replacement character
                if (codePoint < 1 || codePoint > 0x10ffff ||
                    (codePoint > 0xd7ff && codePoint < 0xe000)) {
                    return '\ufffd';
                }
                if (codePoint < 0x10000) {
                    return String.fromCharCode(codePoint);
                }
                return String.fromCodePoint ?
                    String.fromCodePoint(codePoint) :
                    String.fromCharCode(
                        ((codePoint - 0x10000) >> 0x0a) + 0xd800,
                        ((codePoint - 0x10000) % 0x400) + 0xdc00);
            },

        // convert escape sequence in a CSS string or identifier
        // to javascript string with javascript escape sequences
        convertEscapes =
            function(str) {
                return str.replace(reEscapedChars,
                    function(substring, p1, p2) {
                        // unescaped " or '
                        return p2 ? '\\' + p2 :
                            // javascript strings are UTF-16 encoded
                            (/^[0-9a-fA-F]/).test(p1) ? codePointToUTF16(parseInt(p1, 16)) :
                                // \' \"
                                (/^[\\\x22\x27]/).test(p1) ? substring :
                                    // \g \h \. \# etc
                                    p1;
                    }
                );
            },

        // convert escape sequence in a CSS string or identifier
        // to javascript string with characters representations
        unescapeIdentifier =
            function(str) {
                return str.replace(reEscapedChars,
                    function(substring, p1, p2) {
                        // unescaped " or '
                        return p2 ? p2 :
                            // javascript strings are UTF-16 encoded
                            (/^[0-9a-fA-F]/).test(p1) ? stringFromCodePoint(parseInt(p1, 16)) :
                                // \' \"
                                (/^[\\\x22\x27]/).test(p1) ? substring :
                                    // \g \h \. \# etc
                                    p1;
                    }
                );
            },

        /*------------------------------ DOM METHODS -------------------------------*/

        // element by id (raw)
        // @return reference or null
        byIdRaw =
            function(id, elements) {
                var i = -1, element;
                while ((element = elements[++i])) {
                    if (element.getAttribute('id') == id) {
                        break;
                    }
                }
                return element || null;
            },

        // element by id
        // @return reference or null
        _byId = !BUGGY_GEBID ?
            function(id, from) {
                id = (/\\/).test(id) ? unescapeIdentifier(id) : id;
                return from.getElementById && from.getElementById(id) ||
                    byIdRaw(id, from.getElementsByTagName('*'));
            } :
            function(id, from) {
                var element = null;
                id = (/\\/).test(id) ? unescapeIdentifier(id) : id;
                if (XML_DOCUMENT || from.nodeType != 9) {
                    return byIdRaw(id, from.getElementsByTagName('*'));
                }
                if ((element = from.getElementById(id)) &&
                    element.name == id && from.getElementsByName) {
                    return byIdRaw(id, from.getElementsByName(id));
                }
                return element;
            },

        // publicly exposed byId
        // @return reference or null
        byId =
            function(id, from) {
                from || (from = doc);
                if (lastContext !== from) { switchContext(from); }
                return _byId(id, from);
            },

        // elements by tag (raw)
        // @return array
        byTagRaw =
            function(tag, from) {
                var any = tag == '*', element = from, elements = [ ], next = element.firstChild;
                any || (tag = tag.toUpperCase());
                while ((element = next)) {
                    if (element.tagName > '@' && (any || element.tagName.toUpperCase() == tag)) {
                        elements[elements.length] = element;
                    }
                    if ((next = element.firstChild || element.nextSibling)) continue;
                    while (!next && (element = element.parentNode) && element !== from) {
                        next = element.nextSibling;
                    }
                }
                return elements;
            },

        // elements by tag
        // @return array
        _byTag = !BUGGY_GEBTN && NATIVE_SLICE_PROTO ?
            function(tag, from) {
                return XML_DOCUMENT || from.nodeType == 11 ? byTagRaw(tag, from) :
                    slice.call(from.getElementsByTagName(tag), 0);
            } :
            function(tag, from) {
                var i = -1, j = i, data = [ ], element,
                    elements = XML_DOCUMENT || from.nodeType == 11 ?
                        byTagRaw(tag, from) : from.getElementsByTagName(tag);
                if (tag == '*') {
                    while ((element = elements[++i])) {
                        if (element.nodeName > '@') {
                            data[++j] = element;
                        }
                    }
                } else {
                    while ((element = elements[++i])) {
                        data[i] = element;
                    }
                }
                return data;
            },

        // publicly exposed byTag
        // @return array
        byTag =
            function(tag, from) {
                from || (from = doc);
                if (lastContext !== from) { switchContext(from); }
                return _byTag(tag, from);
            },

        // publicly exposed byName
        // @return array
        byName =
            function(name, from) {
                return select('[name="' + name.replace(/\\([^\\]{1})/g, '$1') + '"]', from);
            },

        // elements by class (raw)
        // @return array
        byClassRaw =
            function(name, from) {
                var i = -1, j = i, data = [ ], element, elements = _byTag('*', from), n;
                name = ' ' + (QUIRKS_MODE ? name.toLowerCase() : name) + ' ';
                while ((element = elements[++i])) {
                    n = XML_DOCUMENT ? element.getAttribute('class') : element.className;
                    if (n && n.length && (' ' + (QUIRKS_MODE ? n.toLowerCase() : n).
                        replace(reWhiteSpace, ' ') + ' ').indexOf(name) > -1) {
                        data[++j] = element;
                    }
                }
                return data;
            },

        // elements by class
        // @return array
        _byClass =
            function(name, from) {
                name = QUIRKS_MODE ? name.toLowerCase() : name;
                name = (/\\/).test(name) ? unescapeIdentifier(name) : name;
                return (BUGGY_GEBCN || BUGGY_QUIRKS_GEBCN || XML_DOCUMENT || !from.getElementsByClassName) ?
                    byClassRaw(name, from) : slice.call(from.getElementsByClassName(name));
            },

        // publicly exposed byClass
        // @return array
        byClass =
            function(name, from) {
                from || (from = doc);
                if (lastContext !== from) { switchContext(from); }
                return _byClass(name, from);
            },

        // check element is descendant of container
        // @return boolean
        contains = 'compareDocumentPosition' in root ?
            function(container, element) {
                return (container.compareDocumentPosition(element) & 16) == 16;
            } : 'contains' in root ?
                function(container, element) {
                    return container !== element && container.contains(element);
                } :
                function(container, element) {
                    while ((element = element.parentNode)) {
                        if (element === container) return true;
                    }
                    return false;
                },

        // attribute value
        // @return string
        getAttribute = !BUGGY_GET_ATTRIBUTE && !IE_LT_9 ?
            function(node, attribute) {
                return node.getAttribute(attribute);
            } :
            function(node, attribute) {
                attribute = attribute.toLowerCase();
                if (typeof node[attribute] == 'object') {
                    return node.attributes[attribute] &&
                        node.attributes[attribute].value;
                }
                return (
                    // 'type' can only be read by using native getAttribute
                    attribute == 'type' ? node.getAttribute(attribute) :
                        // specific URI data attributes (parameter 2 to fix IE bug)
                        ATTR_URIDATA[attribute] ? node.getAttribute(attribute, 2) :
                            // boolean attributes should return name instead of true/false
                            ATTR_BOOLEAN[attribute] ? node.getAttribute(attribute) ? attribute : 'false' :
                                (node = node.getAttributeNode(attribute)) && node.value);
            },

        // attribute presence
        // @return boolean
        hasAttribute = !BUGGY_HAS_ATTRIBUTE && !IE_LT_9 ?
            function(node, attribute) {
                return XML_DOCUMENT ?
                    !!node.getAttribute(attribute) :
                    node.hasAttribute(attribute);
            } :
            function(node, attribute) {
                // read the node attribute object
                var obj = node.getAttributeNode(attribute = attribute.toLowerCase());
                return ATTR_DEFAULT[attribute] && attribute != 'value' ?
                    node[ATTR_DEFAULT[attribute]] : obj && obj.specified;
            },

        // check node emptyness
        // @return boolean
        isEmpty =
            function(node) {
                node = node.firstChild;
                while (node) {
                    if (node.nodeType == 3 || node.nodeName > '@') return false;
                    node = node.nextSibling;
                }
                return true;
            },

        // check if element matches the :link pseudo
        // @return boolean
        isLink =
            function(element) {
                return hasAttribute(element,'href') && LINK_NODES[element.nodeName];
            },

        // child position by nodeType
        // @return number
        nthElement =
            function(element, last) {
                var count = 1, succ = last ? 'nextSibling' : 'previousSibling';
                while ((element = element[succ])) {
                    if (element.nodeName > '@') ++count;
                }
                return count;
            },

        // child position by nodeName
        // @return number
        nthOfType =
            function(element, last) {
                var count = 1, succ = last ? 'nextSibling' : 'previousSibling', type = element.nodeName;
                while ((element = element[succ])) {
                    if (element.nodeName == type) ++count;
                }
                return count;
            },

        /*------------------------------- DEBUGGING --------------------------------*/

        // get/set (string/object) working modes
        configure =
            function(option) {
                if (typeof option == 'string') { return !!Config[option]; }
                if (typeof option != 'object') { return Config; }
                for (var i in option) {
                    Config[i] = !!option[i];
                    if (i == 'SIMPLENOT') {
                        matchContexts = { };
                        matchResolvers = { };
                        selectContexts = { };
                        selectResolvers = { };
                        if (!Config[i]) { Config['USE_QSAPI'] = false; }
                    } else if (i == 'USE_QSAPI') {
                        Config[i] = !!option[i] && NATIVE_QSAPI;
                    }
                }
                setIdentifierSyntax();
                reValidator = RegExp(Config.SIMPLENOT ?
                    standardValidator : extendedValidator);
                return true;
            },

        // control user notifications
        emit =
            function(message) {
                if (Config.VERBOSITY) { throw Error(message); }
                if (Config.LOGERRORS && console && console.log) {
                    console.log(message);
                }
            },

        Config = {

            // true to enable caching of result sets, false to disable
            CACHING: false,

            // true to allow CSS escaped identifiers, false to disallow
            ESCAPECHR: true,

            // true to allow identifiers containing non-ASCII (utf-8) chars
            NON_ASCII: true,

            // switch syntax RE, true to use Level 3, false to use Level 2
            SELECTOR3: true,

            // true to allow identifiers containing Unicode (utf-16) chars
            UNICODE16: true,

            // by default do not add missing left/right context
            // to mangled selector strings like "+div" or "ul>"
            // callable Dom.shortcuts method has to be available
            SHORTCUTS: false,

            // true to disable complex selectors nested in
            // ':not()' pseudo-classes as for specifications
            SIMPLENOT: true,

            // true to match lowercase tag names of SVG elements in HTML
            SVG_LCASE: false,

            // strict QSA match all non-unique IDs (false)
            // speed & libs compat match unique ID (true)
            UNIQUE_ID: true,

            // true to follow HTML5 specs handling of ":checked"
            // pseudo-class and similar UI states (indeterminate)
            USE_HTML5: true,

            // true to use browsers native Query Selector API if available
            USE_QSAPI: NATIVE_QSAPI,

            // true to throw exceptions, false to skip throwing exceptions
            VERBOSITY: true,

            // true to print console errors or warnings, false to mute them
            LOGERRORS: true

        },

        /*---------------------------- COMPILER METHODS ----------------------------*/

        // init REs and context
        initialize =
            function(doc) {
                setIdentifierSyntax();
                switchContext(doc, true);
            },

        // set/reset default identifier syntax
        // based on user configuration options
        // rebuild the validator and other REs
        setIdentifierSyntax =
            function() {

                var syntax = '', start = Config['SELECTOR3'] ? '-{2}|' : '';

                Config['NON_ASCII'] && (syntax += '|' + non_asc_chr);
                Config['UNICODE16'] && (syntax += '|' + unicode_chr);
                Config['ESCAPECHR'] && (syntax += '|' + escaped_chr);

                syntax += (Config['UNICODE16'] || Config['ESCAPECHR']) ? '' : '|' + any_esc_chr;

                identifier = '-?(?:' + start + alphalodash + syntax + ')(?:-|[0-9]|' + alphalodash + syntax + ')*';

                // build attribute string
                attrcheck = '(' + quotedvalue + '|' + identifier + ')';
                attributes = whitespace + '*(' + identifier + '(?::' + identifier + ')?)' +
                    whitespace + '*(?:' + operators + whitespace + '*' + attrcheck + ')?' + whitespace + '*' + '(i)?' + whitespace + '*';
                attrmatcher = attributes.replace(attrcheck, '([\\x22\\x27]*)((?:\\\\?.)*?)\\3');

                // build pseudoclass string
                pseudoclass = '((?:' +
                    // an+b parameters or quoted string
                    pseudoparms + '|' + quotedvalue + '|' +
                    // id, class, pseudo-class selector
                    prefixes + identifier + '|' +
                    // nested HTML attribute selector
                    '\\[' + attributes + '\\]|' +
                    // nested pseudo-class selector
                    '\\(.+\\)|' + whitespace + '*|' +
                    // nested pseudos/separators
                    ',)+)';

                // CSS3: syntax scanner and
                // one pass validation only
                // using regular expression
                standardValidator =
                    // discard start
                    '(?=[\\x20\\t\\n\\r\\f]*[^>+~(){}<>])' +
                    // open match group
                    '(' +
                    //universal selector
                    '\\*' +
                    // id/class/tag/pseudo-class identifier
                    '|(?:' + prefixes + identifier + ')' +
                    // combinator selector
                    '|' + combinators +
                    // HTML attribute selector
                    '|\\[' + attributes + '\\]' +
                    // pseudo-classes parameters
                    '|\\(' + pseudoclass + '\\)' +
                    // dom properties selector (extension)
                    '|\\{' + extensions + '\\}' +
                    // selector group separator (comma)
                    '|(?:,|' + whitespace + '*)' +
                    // close match group
                    ')+';

                // only allow simple selectors nested in ':not()' pseudo-classes
                reSimpleNot = RegExp('^(' +
                    '(?!:not)' +
                    '(' + prefixes + identifier +
                    '|\\([^()]*\\))+' +
                    '|\\[' + attributes + '\\]' +
                    ')$');

                // split last, right most, selector group token
                reSplitToken = RegExp('(' +
                    prefixes + identifier + '|' +
                    '\\[' + attributes + '\\]|' +
                    '\\(' + pseudoclass + '\\)|' +
                    '\\\\.|[^\\x20\\t\\n\\r\\f>+~])+', 'g');

                reOptimizeSelector = RegExp(identifier + '|^$');

                reSimpleSelector = RegExp(
                    BUGGY_GEBTN && BUGGY_GEBCN || OPERA ?
                        '^#?' + identifier + '$' : BUGGY_GEBTN ?
                        '^[.#]?' + identifier + '$' : BUGGY_GEBCN ?
                            '^(?:\\*|#' + identifier + ')$' :
                            '^(?:\\*|[.#]?' + identifier + ')$');

                // matches class selectors
                reClass = RegExp('(?:\\[[\\x20\\t\\n\\r\\f]*class\\b|\\.' + identifier + ')');

                Optimize = {
                    ID: RegExp('^\\*?#(' + identifier + ')|' + skip_groups),
                    TAG: RegExp('^(' + identifier + ')|' + skip_groups),
                    CLASS: RegExp('^\\.(' + identifier + '$)|' + skip_groups)
                };

                Patterns.id = RegExp('^#(' + identifier + ')(.*)');
                Patterns.tagName = RegExp('^(' + identifier + ')(.*)');
                Patterns.className = RegExp('^\\.(' + identifier + ')(.*)');
                Patterns.attribute = RegExp('^\\[' + attrmatcher + '\\](.*)');

                Tokens.identifier = identifier;
                Tokens.attributes = attributes;

                // validator for complex selectors in ':not()' pseudo-classes
                extendedValidator = standardValidator.replace(pseudoclass, '.*');

                // validator for standard selectors as default
                reValidator = RegExp(standardValidator);
            },

        // code string reused to build compiled functions
        ACCEPT_NODE = 'r[r.length]=c[k];if(f&&false===f(c[k]))break main;else continue main;',

        // compile a comma separated group of selector
        // @mode boolean true for select, false for match
        // return a compiled function
        compile =
            function(selector, source, mode) {

                var parts = typeof selector == 'string' ? selector.match(reSplitGroup) : selector;

                // ensures that source is a string
                typeof source == 'string' || (source = '');

                if (parts.length == 1) {
                    source += compileSelector(parts[0], mode ? ACCEPT_NODE : 'f&&f(k);return true;', mode);
                } else {
                    // for each selector in the group
                    var i = -1, seen = { }, token;
                    while ((token = parts[++i])) {
                        token = token.replace(reTrimSpaces, '');
                        // avoid repeating the same token
                        // in comma separated group (p, p)
                        if (!seen[token] && (seen[token] = true)) {
                            source += compileSelector(token, mode ? ACCEPT_NODE : 'f&&f(k);return true;', mode);
                        }
                    }
                }

                if (mode) {
                    // for select method
                    return Function('c,s,d,h,g,f',
                        'var N,n,x=0,k=-1,e,r=[];main:while((e=c[++k])){' + source + '}return r;');
                } else {
                    // for match method
                    return Function('e,s,d,h,g,f',
                        'var N,n,x=0,k=e;' + source + 'return false;');
                }
            },

        // compile a CSS3 string selector into ad-hoc javascript matching function
        // @return string (to be compiled)
        compileSelector =
            function(selector, source, mode) {

                var a, b, n, k = 0, expr, match, result, status, test, type;

                while (selector) {

                    k++;

                    // *** Universal selector
                    // * match all (empty block, do not remove)
                    if ((match = selector.match(Patterns.universal))) {
                        // do nothing, handled in the compiler where
                        // BUGGY_GEBTN return comment nodes (ex: IE)
                        expr = '';
                    }

                    // *** ID selector
                    // #Foo Id case sensitive
                    else if ((match = selector.match(Patterns.id))) {
                        // document can contain conflicting elements (id/name)
                        // prototype selector unit need this method to recover bad HTML forms
                        match[1] = (/\\/).test(match[1]) ? convertEscapes(match[1]) : match[1];
                        source = 'if(' + (XML_DOCUMENT ?
                            's.getAttribute(e,"id")' :
                            '(e.submit?s.getAttribute(e,"id"):e.id)') +
                            '=="' + match[1] + '"' +
                            '){' + source + '}';
                    }

                    // *** Type selector
                    // Foo Tag (case insensitive)
                    else if ((match = selector.match(Patterns.tagName))) {
                        // both tagName and nodeName properties may be upper/lower case
                        // depending on their creation NAMESPACE in createElementNS()
                        test = Config.SVG_LCASE ? '||e.nodeName=="' + match[1].toLowerCase() + '"' : '';
                        source = 'if(e.nodeName' + (XML_DOCUMENT ?
                            '=="' + match[1] + '"' : '.toUpperCase()' +
                            '=="' + match[1].toUpperCase() + '"' + test) +
                            '){' + source + '}';
                    }

                    // *** Class selector
                    // .Foo Class (case sensitive)
                    else if ((match = selector.match(Patterns.className))) {
                        // W3C CSS3 specs: element whose "class" attribute has been assigned a
                        // list of whitespace-separated values, see section 6.4 Class selectors
                        // and notes at the bottom; explicitly non-normative in this specification.
                        match[1] = (/\\/).test(match[1]) ? convertEscapes(match[1]) : match[1];
                        match[1] = QUIRKS_MODE ? match[1].toLowerCase() : match[1];
                        source = 'if((n=' + (XML_DOCUMENT ?
                            's.getAttribute(e,"class")' : 'e.className') +
                            ')&&n.length&&(" "+' + (QUIRKS_MODE ? 'n.toLowerCase()' : 'n') +
                            '.replace(/' + whitespace + '+/g," ")+" ").indexOf(" ' + match[1] + ' ")>-1' +
                            '){' + source + '}';
                    }

                    // *** Attribute selector
                    // [attr] [attr=value] [attr="value"] [attr='value'] and !=, *=, ~=, |=, ^=, $=
                    // case sensitivity is treated differently depending on the document type (see map)
                    else if ((match = selector.match(Patterns.attribute))) {

                        // xml namespaced attribute ?
                        expr = match[1].split(':');
                        expr = expr.length == 2 ? expr[1] : expr[0] + '';

                        if (match[2] && !Operators[match[2]]) {
                            emit('Unsupported operator in attribute selectors "' + selector + '"');
                            return '';
                        }

                        test = 'false';

                        // replace Operators parameter if needed
                        if (match[2] && match[4] && (test = Operators[match[2]])) {
                            match[4] = (/\\/).test(match[4]) ? convertEscapes(match[4]) : match[4];
                            // case treatment depends on document type
                            type = match[5] == 'i' || HTML_TABLE[expr.toLowerCase()];
                            test = test.replace(/\%m/g, type ? match[4].toLowerCase() : match[4]);
                        } else if (match[2] == '!=' || match[2] == '=') {
                            test = 'n' + match[2] + '=""';
                        }

                        source = 'if(n=s.hasAttribute(e,"' + match[1] + '")){' +
                            (match[2] ? 'n=s.getAttribute(e,"' + match[1] + '")' : '') +
                            (type && match[2] ? '.toLowerCase();' : ';') +
                            'if(' + (match[2] ? test : 'n') + '){' + source + '}}';

                    }

                    // *** Adjacent sibling combinator
                    // E + F (F adiacent sibling of E)
                    else if ((match = selector.match(Patterns.adjacent))) {
                        source = NATIVE_TRAVERSAL_API ?
                            'var N' + k + '=e;if((e=e.previousElementSibling)){' + source + '}e=N' + k + ';' :
                            'var N' + k + '=e;while((e=e.previousSibling)){if(e.nodeType==1){' + source + 'break;}}e=N' + k + ';';
                    }

                    // *** General sibling combinator
                    // E ~ F (F relative sibling of E)
                    else if ((match = selector.match(Patterns.relative))) {
                        source = NATIVE_TRAVERSAL_API ?
                            'var N' + k + '=e;while((e=e.previousElementSibling)){' + source + '}e=N' + k + ';' :
                            'var N' + k + '=e;while((e=e.previousSibling)){if(e.nodeType==1){' + source + '}}e=N' + k + ';';
                    }

                    // *** Child combinator
                    // E > F (F children of E)
                    else if ((match = selector.match(Patterns.children))) {
                        source = 'var N' + k + '=e;if((e=e.parentNode)&&e.nodeType==1){' + source + '}e=N' + k + ';';
                    }

                    // *** Descendant combinator
                    // E F (E ancestor of F)
                    else if ((match = selector.match(Patterns.ancestor))) {
                        source = 'var N' + k + '=e;while((e=e.parentNode)&&e.nodeType==1){' + source + '}e=N' + k + ';';
                    }

                    // *** Structural pseudo-classes
                    // :root, :empty,
                    // :first-child, :last-child, :only-child,
                    // :first-of-type, :last-of-type, :only-of-type,
                    // :nth-child(), :nth-last-child(), :nth-of-type(), :nth-last-of-type()
                    else if ((match = selector.match(Patterns.spseudos)) && match[1]) {

                        switch (match[1]) {
                            case 'root':
                                // element root of the document
                                if (match[3]) {
                                    source = 'if(e===h||s.contains(h,e)){' + source + '}';
                                } else {
                                    source = 'if(e===h){' + source + '}';
                                }
                                break;

                            case 'empty':
                                // element that has no children
                                source = 'if(s.isEmpty(e)){' + source + '}';
                                break;

                            default:
                                if (match[1] && match[2]) {
                                    if (match[2] == 'n') {
                                        source = 'if(e!==h){' + source + '}';
                                        break;
                                    } else if (match[2] == 'even') {
                                        a = 2;
                                        b = 0;
                                    } else if (match[2] == 'odd') {
                                        a = 2;
                                        b = 1;
                                    } else {
                                        // assumes correct "an+b" format, "b" before "a" to keep "n" values
                                        b = ((n = match[2].match(/(-?\d+)$/)) ? parseInt(n[1], 10) : 0);
                                        a = ((n = match[2].match(/(-?\d*)n/i)) ? parseInt(n[1], 10) : 0);
                                        if (n && n[1] == '-') a = -1;
                                    }

                                    // build test expression out of structural pseudo (an+b) parameters
                                    // see here: http://www.w3.org/TR/css3-selectors/#nth-child-pseudo
                                    test = a > 1 ?
                                        (/last/i.test(match[1])) ? '(n-(' + b + '))%' + a + '==0' :
                                            'n>=' + b + '&&(n-(' + b + '))%' + a + '==0' : a < -1 ?
                                            (/last/i.test(match[1])) ? '(n-(' + b + '))%' + a + '==0' :
                                                'n<=' + b + '&&(n-(' + b + '))%' + a + '==0' : a === 0 ?
                                                'n==' + b : a == -1 ? 'n<=' + b : 'n>=' + b;

                                    // 4 cases: 1 (nth) x 4 (child, of-type, last-child, last-of-type)
                                    source =
                                        'if(e!==h){' +
                                        'n=s[' + (/-of-type/i.test(match[1]) ? '"nthOfType"' : '"nthElement"') + ']' +
                                        '(e,' + (/last/i.test(match[1]) ? 'true' : 'false') + ');' +
                                        'if(' + test + '){' + source + '}' +
                                        '}';

                                } else {
                                    // 6 cases: 3 (first, last, only) x 1 (child) x 2 (-of-type)
                                    a = /first/i.test(match[1]) ? 'previous' : 'next';
                                    n = /only/i.test(match[1]) ? 'previous' : 'next';
                                    b = /first|last/i.test(match[1]);

                                    type = /-of-type/i.test(match[1]) ? '&&n.nodeName!=e.nodeName' : '&&n.nodeName<"@"';

                                    source = 'if(e!==h){' +
                                        ( 'n=e;while((n=n.' + a + 'Sibling)' + type + ');if(!n){' + (b ? source :
                                            'n=e;while((n=n.' + n + 'Sibling)' + type + ');if(!n){' + source + '}') + '}' ) + '}';
                                }
                                break;
                        }

                    }

                    // *** negation, user action and target pseudo-classes
                    // *** UI element states and dynamic pseudo-classes
                    // CSS4 :matches
                    // CSS3 :not, :checked, :enabled, :disabled, :target
                    // CSS3 :active, :hover, :focus
                    // CSS3 :link, :visited
                    else if ((match = selector.match(Patterns.dpseudos)) && match[1]) {

                        switch (match[1].match(/^\w+/)[0]) {
                            // CSS4 matches pseudo-class
                            case 'matches':
                                expr = match[3].replace(reTrimSpaces, '');
                                source = 'if(s.match(e, "' + expr.replace(/\x22/g, '\\"') + '",g)){' + source +'}';
                                break;

                            // CSS3 negation pseudo-class
                            case 'not':
                                // compile nested selectors, DO NOT pass the callback parameter
                                // SIMPLENOT allow disabling complex selectors nested
                                // in ':not()' pseudo-classes, breaks some test units
                                expr = match[3].replace(reTrimSpaces, '');

                                if (Config.SIMPLENOT && !reSimpleNot.test(expr)) {
                                    // see above, log error but continue execution
                                    emit('Negation pseudo-class only accepts simple selectors "' + selector + '"');
                                    return '';
                                } else {
                                    if ('compatMode' in doc) {
                                        source = 'if(!' + compile(expr, '', false) + '(e,s,d,h,g)){' + source + '}';
                                    } else {
                                        source = 'if(!s.match(e, "' + expr.replace(/\x22/g, '\\"') + '",g)){' + source +'}';
                                    }
                                }
                                break;

                            // CSS3 UI element states
                            case 'checked':
                                // for radio buttons checkboxes (HTML4) and options (HTML5)
                                source = 'if((typeof e.form!=="undefined"&&(/^(?:radio|checkbox)$/i).test(e.type)&&e.checked)' +
                                    (Config.USE_HTML5 ? '||(/^option$/i.test(e.nodeName)&&(e.selected||e.checked))' : '') +
                                    '){' + source + '}';
                                break;
                            case 'disabled':
                                // does not consider hidden input fields
                                source = 'if(((typeof e.form!=="undefined"' +
                                    (Config.USE_HTML5 ? '' : '&&!(/^hidden$/i).test(e.type)') +
                                    ')||s.isLink(e))&&e.disabled===true){' + source + '}';
                                break;
                            case 'enabled':
                                // does not consider hidden input fields
                                source = 'if(((typeof e.form!=="undefined"' +
                                    (Config.USE_HTML5 ? '' : '&&!(/^hidden$/i).test(e.type)') +
                                    ')||s.isLink(e))&&e.disabled===false){' + source + '}';
                                break;

                            // CSS3 lang pseudo-class
                            case 'lang':
                                test = '';
                                if (match[2]) test = match[2].substr(0, 2) + '-';
                                source = 'do{(n=e.lang||"").toLowerCase();' +
                                    'if((n==""&&h.lang=="' + match[2].toLowerCase() + '")||' +
                                    '(n&&(n=="' + match[2].toLowerCase() +
                                    '"||n.substr(0,3)=="' + test.toLowerCase() + '")))' +
                                    '{' + source + 'break;}}while((e=e.parentNode)&&e!==g);';
                                break;

                            // CSS3 target pseudo-class
                            case 'target':
                                source = 'if(e.id==d.location.hash.slice(1)){' + source + '}';
                                break;

                            // CSS3 dynamic pseudo-classes
                            case 'link':
                                source = 'if(s.isLink(e)&&!e.visited){' + source + '}';
                                break;
                            case 'visited':
                                source = 'if(s.isLink(e)&&e.visited){' + source + '}';
                                break;

                            // CSS3 user action pseudo-classes IE & FF3 have native support
                            // these capabilities may be emulated by some event managers
                            case 'active':
                                if (XML_DOCUMENT) break;
                                source = 'if(e===d.activeElement){' + source + '}';
                                break;
                            case 'hover':
                                if (XML_DOCUMENT) break;
                                source = 'if(e===d.hoverElement){' + source + '}';
                                break;
                            case 'focus':
                                if (XML_DOCUMENT) break;
                                source = NATIVE_FOCUS ?
                                    'if(e===d.activeElement&&d.hasFocus()&&(e.type||e.href||typeof e.tabIndex=="number")){' + source + '}' :
                                    'if(e===d.activeElement&&(e.type||e.href)){' + source + '}';
                                break;

                            // CSS2 selected pseudo-classes, not part of current CSS3 drafts
                            // the 'selected' property is only available for option elements
                            case 'selected':
                                // fix Safari selectedIndex property bug
                                expr = BUGGY_SELECTED ? '||(n=e.parentNode)&&n.options[n.selectedIndex]===e' : '';
                                source = 'if(/^option$/i.test(e.nodeName)&&(e.selected||e.checked' + expr + ')){' + source + '}';
                                break;

                            default:
                                break;
                        }

                    }

                    else if ((match = selector.match(Patterns.epseudos)) && match[1]) {
                        source = 'if(!(/1|11/).test(e.nodeType)){' + source + '}';
                    }

                    else {

                        // this is where external extensions are
                        // invoked if expressions match selectors
                        expr = false;
                        status = false;
                        for (expr in Selectors) {
                            if ((match = selector.match(Selectors[expr].Expression)) && match[1]) {
                                result = Selectors[expr].Callback(match, source);
                                if ('match' in result) { match = result.match; }
                                source = result.source;
                                status = result.status;
                                if (status) { break; }
                            }
                        }

                        // if an extension fails to parse the selector
                        // it must return a false boolean in "status"
                        if (!status) {
                            // log error but continue execution, don't throw real exceptions
                            // because blocking following processes maybe is not a good idea
                            emit('Unknown pseudo-class selector "' + selector + '"');
                            return '';
                        }

                        if (!expr) {
                            // see above, log error but continue execution
                            emit('Unknown token in selector "' + selector + '"');
                            return '';
                        }

                    }

                    // error if no matches found by the pattern scan
                    if (!match) {
                        emit('Invalid syntax in selector "' + selector + '"');
                        return '';
                    }

                    // ensure "match" is not null or empty since
                    // we do not throw real DOMExceptions above
                    selector = match && match[match.length - 1];
                }

                return source;
            },

        /*----------------------------- QUERY METHODS ------------------------------*/

        // match element with selector
        // @return boolean
        match =
            function(element, selector, from, callback) {

                var parts;

                if (!(element && element.nodeType == 1)) {
                    emit('Invalid element argument');
                    return false;
                } else if (typeof selector != 'string') {
                    emit('Invalid selector argument');
                    return false;
                } else if (from && from.nodeType == 1 && !contains(from, element)) {
                    return false;
                } else if (lastContext !== from) {
                    // reset context data when it changes
                    // and ensure context is set to a default
                    switchContext(from || (from = element.ownerDocument));
                }

                // normalize the selector string, remove [\n\r\f]
                // whitespace, replace codepoints 0 with '\ufffd'
                // trim non-relevant leading/trailing whitespaces
                selector = selector.
                replace(reTrimSpaces, '').
                replace(/\x00|\\$/g, '\ufffd');

                Config.SHORTCUTS && (selector = Dom.shortcuts(selector, element, from));

                if (lastMatcher != selector) {
                    // process valid selector strings
                    if ((parts = selector.match(reValidator)) && parts[0] == selector) {
                        isSingleMatch = (parts = selector.match(reSplitGroup)).length < 2;
                        // save passed selector
                        lastMatcher = selector;
                        lastPartsMatch = parts;
                    } else {
                        emit('The string "' + selector + '", is not a valid CSS selector');
                        return false;
                    }
                } else parts = lastPartsMatch;

                // compile matcher resolvers if necessary
                if (!matchResolvers[selector] || matchContexts[selector] !== from) {
                    matchResolvers[selector] = compile(isSingleMatch ? [selector] : parts, '', false);
                    matchContexts[selector] = from;
                }

                return matchResolvers[selector](element, Snapshot, doc, root, from, callback);
            },

        // select only the first element
        // matching selector (document ordered)
        first =
            function(selector, from) {
                return select(selector, from, function() { return false; })[0] || null;
            },

        // select elements matching selector
        // using new Query Selector API
        // or cross-browser client API
        // @return array
        select =
            function(selector, from, callback) {

                var i, changed, element, elements, parts, token, original = selector;

                if (arguments.length === 0) {
                    emit('Not enough arguments');
                    return [ ];
                } else if (typeof selector != 'string') {
                    return [ ];
                } else if (from && !(/1|9|11/).test(from.nodeType)) {
                    emit('Invalid or illegal context element');
                    return [ ];
                } else if (lastContext !== from) {
                    // reset context data when it changes
                    // and ensure context is set to a default
                    switchContext(from || (from = doc));
                }

                if (Config.CACHING && (elements = Dom.loadResults(original, from, doc, root))) {
                    return callback ? concatCall([ ], elements, callback) : elements;
                }

                // normalize the selector string, remove [\n\r\f]
                // whitespace, replace codepoints 0 with '\ufffd'
                // trim non-relevant leading/trailing whitespaces
                selector = selector.
                replace(reTrimSpaces, '').
                replace(/\x00|\\$/g, '\ufffd');

                if (!OPERA_QSAPI && reSimpleSelector.test(selector)) {
                    switch (selector.charAt(0)) {
                        case '#':
                            if (Config.UNIQUE_ID) {
                                elements = (element = _byId(selector.slice(1), from)) ? [ element ] : [ ];
                            }
                            break;
                        case '.':
                            elements = _byClass(selector.slice(1), from);
                            break;
                        default:
                            elements = _byTag(selector, from);
                            break;
                    }
                }

                else if (!XML_DOCUMENT && Config.USE_QSAPI &&
                    !(BUGGY_QUIRKS_QSAPI && reClass.test(selector)) &&
                    !RE_BUGGY_QSAPI.test(selector)) {
                    try {
                        elements = from.querySelectorAll(selector);
                    } catch(e) { }
                }

                if (elements) {
                    elements = callback ? concatCall([ ], elements, callback) :
                        NATIVE_SLICE_PROTO ? slice.call(elements) : concatList([ ], elements);
                    Config.CACHING && Dom.saveResults(original, from, doc, elements);
                    return elements;
                }

                Config.SHORTCUTS && (selector = Dom.shortcuts(selector, from));

                if ((changed = lastSelector != selector)) {
                    // process valid selector strings
                    if ((parts = selector.match(reValidator)) && parts[0] == selector) {
                        isSingleSelect = (parts = selector.match(reSplitGroup)).length < 2;
                        // save passed selector
                        lastSelector = selector;
                        lastPartsSelect = parts;
                    } else {
                        emit('The string "' + selector + '", is not a valid CSS selector');
                        return [ ];
                    }
                } else parts = lastPartsSelect;

                // commas separators are treated sequentially to maintain order
                if (from.nodeType == 11) {

                    elements = byTagRaw('*', from);

                } else if (!XML_DOCUMENT && isSingleSelect) {

                    if (changed) {
                        // get right most selector token
                        parts = selector.match(reSplitToken);
                        token = parts[parts.length - 1];

                        // only last slice before :not rules
                        lastSlice = token.split(':not');
                        lastSlice = lastSlice[lastSlice.length - 1];

                        // position where token was found
                        lastPosition = selector.length - token.length;
                    }

                    // ID optimization RTL, to reduce number of elements to visit
                    if (Config.UNIQUE_ID && lastSlice && (parts = lastSlice.match(Optimize.ID)) && (token = parts[1])) {
                        if ((element = _byId(token, from))) {
                            if (match(element, selector)) {
                                callback && callback(element);
                                elements = [element];
                            } else elements = [ ];
                        }
                    }

                    // ID optimization LTR, to reduce selection context searches
                    else if (Config.UNIQUE_ID && (parts = selector.match(Optimize.ID)) && (token = parts[1])) {
                        if ((element = _byId(token, doc))) {
                            if ('#' + token == selector) {
                                callback && callback(element);
                                elements = [element];
                            } else if (/[>+~]/.test(selector)) {
                                from = element.parentNode;
                            } else {
                                from = element;
                            }
                        } else elements = [ ];
                    }

                    if (elements) {
                        Config.CACHING && Dom.saveResults(original, from, doc, elements);
                        return elements;
                    }

                    if (!NATIVE_GEBCN && lastSlice && (parts = lastSlice.match(Optimize.TAG)) && (token = parts[1])) {
                        if ((elements = _byTag(token, from)).length === 0) { return [ ]; }
                        selector = selector.slice(0, lastPosition) + selector.slice(lastPosition).replace(token, '*');
                    }

                    else if (lastSlice && (parts = lastSlice.match(Optimize.CLASS)) && (token = parts[1])) {
                        if ((elements = _byClass(token, from)).length === 0) { return [ ]; }
                        selector = selector.slice(0, lastPosition) + selector.slice(lastPosition).replace('.' + token,
                            reOptimizeSelector.test(selector.charAt(selector.indexOf(token) - 1)) ? '' : '*');
                    }

                    else if ((parts = selector.match(Optimize.CLASS)) && (token = parts[1])) {
                        if ((elements = _byClass(token, from)).length === 0) { return [ ]; }
                        for (i = 0, els = [ ]; elements.length > i; ++i) {
                            els = concatList(els, elements[i].getElementsByTagName('*'));
                        }
                        elements = els;
                        selector = selector.slice(0, lastPosition) + selector.slice(lastPosition).replace('.' + token,
                            reOptimizeSelector.test(selector.charAt(selector.indexOf(token) - 1)) ? '' : '*');
                    }

                    else if (NATIVE_GEBCN && lastSlice && (parts = lastSlice.match(Optimize.TAG)) && (token = parts[1])) {
                        if ((elements = _byTag(token, from)).length === 0) { return [ ]; }
                        selector = selector.slice(0, lastPosition) + selector.slice(lastPosition).replace(token, '*');
                    }

                }

                if (!elements) {
                    if (IE_LT_9) {
                        elements = /^(?:applet|object)$/i.test(from.nodeName) ? from.children : byTagRaw('*', from);
                    } else {
                        elements = from.getElementsByTagName('*');
                    }
                }
                // end of prefiltering pass

                // compile selector resolver if necessary
                if (!selectResolvers[selector] || selectContexts[selector] !== from) {
                    selectResolvers[selector] = compile(isSingleSelect ? [selector] : parts, '', true);
                    selectContexts[selector] = from;
                }

                elements = selectResolvers[selector](elements, Snapshot, doc, root, from, callback);

                Config.CACHING && Dom.saveResults(original, from, doc, elements);

                return elements;
            },

        /*-------------------------------- STORAGE ---------------------------------*/

        // empty function handler
        FN = function(x) { return x; },

        // compiled match functions returning booleans
        matchContexts = { },
        matchResolvers = { },

        // compiled select functions returning collections
        selectContexts = { },
        selectResolvers = { },

        // used to pass methods to compiled functions
        Snapshot = {

            // element indexing methods
            nthElement: nthElement,
            nthOfType: nthOfType,

            // element inspection methods
            getAttribute: getAttribute,
            hasAttribute: hasAttribute,

            // element selection methods
            byClass: _byClass,
            byName: byName,
            byTag: _byTag,
            byId: _byId,

            // helper/check methods
            contains: contains,
            isEmpty: isEmpty,
            isLink: isLink,

            // selection/matching
            select: select,
            match: match
        },

        /*------------------------------- PUBLIC API -------------------------------*/

        // code referenced by extensions
        Dom = {

            ACCEPT_NODE: ACCEPT_NODE,

            // retrieve element by id attr
            byId: byId,

            // retrieve elements by tag name
            byTag: byTag,

            // retrieve elements by name attr
            byName: byName,

            // retrieve elements by class name
            byClass: byClass,

            // read the value of the attribute
            // as was in the original HTML code
            getAttribute: getAttribute,

            // check for the attribute presence
            // as was in the original HTML code
            hasAttribute: hasAttribute,

            // element match selector, return boolean true/false
            match: match,

            // first element match only, return element or null
            first: first,

            // elements matching selector, starting from element
            select: select,

            // compile selector into ad-hoc javascript resolver
            compile: compile,

            // check that two elements are ancestor/descendant
            contains: contains,

            // handle selector engine configuration settings
            configure: configure,

            // initialize caching for each document
            setCache: FN,

            // load previously collected result set
            loadResults: FN,

            // save previously collected result set
            saveResults: FN,

            // handle missing context in selector strings
            shortcuts: FN,

            // log resolvers errors/warnings
            emit: emit,

            // options enabing specific engine functionality
            Config: Config,

            // pass methods references to compiled resolvers
            Snapshot: Snapshot,

            // operators descriptor
            // for attribute operators extensions
            Operators: Operators,

            // selectors descriptor
            // for pseudo-class selectors extensions
            Selectors: Selectors,

            // export validators REs
            Tokens: Tokens,

            // export version string
            Version: version,

            // add or overwrite user defined operators
            registerOperator:
                function(symbol, resolver) {
                    Operators[symbol] || (Operators[symbol] = resolver);
                },

            // add selector patterns for user defined callbacks
            registerSelector:
                function(name, rexp, func) {
                    Selectors[name] || (Selectors[name] = {
                        Expression: rexp,
                        Callback: func
                    });
                }

        };

    /*---------------------------------- INIT ----------------------------------*/

    // init context specific variables
    initialize(doc);

    return Dom;
});